package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月6日
*时间：上午11:52:24
*/
public class Q4 {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        int ugly[] = new int[n];
        ugly[0] = 1;
        int count = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        while (count < n) {
            int m2 = ugly[i2] * 2;
            int m3 = ugly[i3] * 3;
            int m5 = ugly[i5] * 5;
            int min = Math.min(m2, Math.min(m3, m5));
            if (min == m2)
                i2++;
            if (min == m3)
                i3++;
            if (min == m5)
                i5++;
            ugly[count++] = min;
        }
        return ugly[n - 1];
    }

    @Test
    public void testA() {
        System.out.println(nthUglyNumber(1665));
    }
}
